--题目：输入一个整数和一棵二元树。从树的根结点开始往下访问一直到叶结点所经过的所有结点形成一条路径。打印出和与输入整数相等的所有路径。
require("test01");


--先创建一个AVG树
local data = {10,5,12,4,7};
local root = nil ;
for i=1,#data do
	root = insertNode(data[i],root);
end

list = {} ;

local function dumpPath(list)
	local str = "" ;
	for i=1,#list do
		str = str .. list[i].. ",";
	end
	print(str);
end

dumpAVGTree(root);
function searchPathList(pNode,sumValue,desvalue,list)
	if(not pNode) then
		return ;
	end
	if(not pNode.m_pLeft and not pNode.m_pRight) then
		if(pNode.m_nvalue + sumValue == desvalue) then
		 table.insert(list,pNode.m_nvalue);
		 dumpPath(list);
		 table.remove(list);
		end
	else
		sumValue = sumValue + pNode.m_nvalue ;
		--大于就剪枝了
		if(sumValue>desvalue) then
			return ;
		end
		table.insert(list,pNode.m_nvalue);
		if(pNode.m_pLeft) then
			searchPathList(pNode.m_pLeft,sumValue,desvalue,list);
		end
		
		if(pNode.m_pRight) then
			searchPathList(pNode.m_pRight,sumValue,desvalue,list);
		end
		table.remove(list);
	end
	
end

searchPathList(root,0,22,list);

